File systems store files and store information about files. The information stored in files may be referred to as data. The information about files may be referred to as metadata. The metadata may include, for example, a file name, a file size, and other information. Some of the metadata for an individual file may be stored in a data structure known as an inode. The inodes and metadata for a file system may be stored collectively. Different approaches may be used to protect files and information about files associated with a file system. For example, an object store may interact with an archive system to store a file or information about a file located in a primary storage space (e.g., disk). To insure data protection, different approaches for storing redundant copies of a file or portions of a file have been employed. Erasure codes are one such approach.
An erasure code is a forward error correction (FEC) code for the binary erasure channel. The FEC facilitates transforming a message of k symbols into a longer message with n symbols such that the original message can be recovered from a subset of the n symbols, k and n being integers. The original message may be, for example, a file. The fraction r=k/n is called the code rate, and the fraction k′/k, where k′ denotes the number of symbols required for recovery, is called the reception efficiency. Optimal erasure codes have the property that any k out of the n code word symbols suffice to recover the original message. Optimal codes may require extensive memory usage, CPU time, or other resources when n is large.
Erasure codes are described in coding theory. Coding theory is the study of the properties of codes and their fitness for a certain purpose (e.g., backing up files). Codes may be used for applications including, for example, data compression, cryptography, error-correction, and network coding. Coding theory involves data compression, which may also be referred to as source coding, and error correction, which may also be referred to as channel coding. Fountain codes are one type of erasure codes.
Fountain codes have the property that a potentially limitless sequence of encoding symbols may be generated from a given set of source symbols in a manner that supports ideally recovering the original source symbols from any subset of the encoding symbols of size equal to or larger than the number of source symbols. A fountain code may be optimal if the original k source symbols can be recovered from any k encoding symbols, k being an integer. Fountain codes may have efficient encoding and decoding algorithms that support recovering the original k source symbols from any k′ of the encoding symbols with high probability, where k′ is just slightly larger than k. A rateless code is distinguished from a code that exhibits a fixed code rate.
Using a fixed-rate erasure code, a receiver missing a source symbol faces the coupon collector's problem. The coupon collector's problem involves a receiver successfully receiving an encoding symbol that it does not already have. The coupon collector's problem becomes more apparent when a traditional short-length erasure code is used because the file being backed up is split into several blocks, each serving as an original message and each being separately encoded. In this scenario, the receiver must now collect the required number of missing encoding symbols for each block. Conversely, using a rateless erasure code (e.g., fountain code), a receiver need only be able to retrieve any subset of encoding symbols larger than the set of source symbols.
Object based storage systems may employ rateless erasure code technology (e.g., fountain codes) to provide a flexible level of data redundancy. The appropriate or even optimal level of data redundancy produced using a rateless erasure code system may depend, for example, on the value of the data. The actual level of redundancy achieved using a rateless erasure code system may depend, for example, on the difference between the number of readable redundancy blocks (e.g., erasure codes) written by the system and the number of redundancy blocks needed to reconstruct the original data. For example, if twenty redundancy blocks are written and only eleven redundancy blocks are needed to reconstruct the original data that was protected by writing the redundancy blocks, then the original data may be reconstructed even if nine of the redundancy blocks are damaged or otherwise unavailable.
Conventional systems may use a pre-defined setting to determine whether a store operation will operate synchronously or asynchronously. The store operation may be the operation that is tasked with writing the redundancy blocks (e.g., erasure codes) in the object store using erasure codes. A synchronous store operation may normally generate all the redundancy blocks to be written before completing the store operation but on occasion may operate one block at a time. This approach yields the result that the optimal redundancy level is in place before the store operation signals its completion. Conversely, an asynchronous store operation may not generate all the redundancy blocks to be written before completing the store operation. An asynchronous store operation may generate the minimal number of redundancy blocks required to achieve some redundancy and protection, may then signal completion of the store operation, and may then write additional redundancy blocks until an optimal redundancy or protection is achieved. An asynchronous store operation may be faster than a synchronous store operation for achieving minimal protection. Conventional systems may be caught on the horns of a dilemma that pits achieving faster but sub-optimal redundancy against achieving slower but optimal redundancy.
Archive systems may choose not to employ the faster asynchronous store approach to avoid producing less than optimal redundancy. For example, when an archive system uses an object storage to provide a redundant tertiary copy of an original data file, it may be unacceptable to employ the faster asynchronous store approach that causes a store operation to report completion before optimal redundancy is actually achieved. Consider an archive system that uses a conventional RAID (redundant array of independent disks) (e.g., RAID-6) to provide a level of redundancy for the primary storage of original data. If the asynchronous approach is employed, and the store operation that is intended to produce another level of redundancy for the primary storage of the original data is allowed to indicate completion before optimal redundancy is actually achieved, then a desired or even required level of redundancy may not be achieved and data may be at risk. Additional risk may arise when the completion of the store operation allows the primary data storage to release the first copy of the original data. Therefore, conventional archive systems interacting with object storage systems may have been constrained to always use the slower synchronous approach.